#include<iostream>
#include<stack>
using namespace std;
void swap(int* a,int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void InsertSort(int* a, int n)
{

	for (int i = 0; i < n-1; i++)
	{
		int end = i;
		int next = a[end + 1];
		while (end >= 0)
		{
			if (next < a[end])
			{
				a[end + 1] = a[end];
				end -= 1;


			}
			else
			{
				break;
			}

		}
		a[end+1] = next;
	}
}
void BubbleSort(int* a, int n)
{

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - i-1; j++)
		{
			if (a[j] > a[j + 1])
			{
				swap(a[j], a[j + 1]);
			}




		}





	}

}
void SelectSort(int* a, int n)
{
	
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int maxi = begin;
		int mini = begin;
		for (int i = begin+1; i <= end; i++)
		{
		  
			if (a[i] < a[mini])
			{
				
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				
				maxi = i;

			}
		}
		swap(&a[begin], &a[mini]);  // 10       1
			if (maxi == begin)
			{
				maxi = mini;
			}
		swap(&a[end], &a[maxi]);
		begin++;
		end--;

	}






}
void ShellSort(int* a, int n)
{
	int gap = 3;
	while(gap>=1)
	{  
		for (int j = 0; j < gap; j++)
		{
			for (int i = j; i <n - gap; i += gap)
			{
				int end = i;
				int tmp = a[end + gap];
				while (end >= 0)
				{

					if (tmp < a[end])
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tmp;
			}
		}
	            gap /= 2;
	
	
	}

}
int PartSort1(int* a, int left, int right)
{
	int key = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[key])
		{

			right--;

		}
		while (left < right && a[left] <= a[key])
		{
            left++;

		}
		swap(&a[left], &a[right]);
		
	}
	swap(&a[left], &a[key]);
	return left;

}
int PartSort2(int* a, int left, int right)
{
	int key = a[left];
	int pole = left;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{

			right--;

		}
		a[pole] = a[right];
		pole = right;
		while (left < right && a[left]<=key)
		{

			left++;

		}
		a[pole] = a[left];
		pole = left;
	}
	a[pole] = key;
	return pole;

}
int PartSort3(int* a, int left, int right)
{
	int prev = left;
	int cur = prev + 1;
	int key = left;
	while (cur <= right)
	{
		 
	
		 if (a[cur] <= a[key])
		{

			prev++;
			swap(&a[cur], &a[prev]);

		}

		 cur++;






	}
	swap(&a[key], &a[prev]);
	return prev;


}
//void QuickSort(int* a, int begin, int end)
//{
//
//	if (begin >= end)
//		return;
//	int ret = PartSort3(a, begin, end);
//
//	QuickSort(a, begin, ret - 1);
//	QuickSort(a, ret+1,end);
//
//}
void QuickSort(int* a, int begin, int end)
{
	stack<int>st;

	st.push(begin);
	st.push(end);
	while (!st.empty())
	{
		int  right = st.top();
		st.pop();
		int left = st.top();
		st.pop();

     int mid=PartSort3(a, left, right);

	 if (mid + 1 < right)
	 {
		 st.push(mid + 1);
		 st.push(right);

	 }
	 if (mid - 1 > left)
	 {
		 st.push(left);
		 st.push(mid-1);

	 }





	}


}
int main()
{
	int arr[] = { 10,9,1 ,3,7,6,2,4,5};
	//InsertSort(arr, 8);
	//BubbleSort(arr, 8);
	//SelectSort(arr, 8);
	 //ShellSort(arr, 9);
	QuickSort(arr, 0, 8);
	for (int i = 0; i <9; i++)
	{
		cout << arr[i] << " ";
	
	}

}